#ifndef KD_TREE_H// Use a unique identifier for every file.
#define KD_TREE_H

#include "stdafx.h"
#include "Maths.h"
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
class KdNode
{
public:
	vector<Triangle<T>* > children;
	KdNode<T> *rightChild;
	KdNode<T> *leftChild;
	int plandeSubDivision;
	T boundary;
	bool hasChildren;
	T medianBoundary;
	BoundingBox<T> *boundingBox;
	KdNode <T> *parentNode;



	KdNode(KdNode<T> *parentNode)
	{
		this->parentNode = parentNode;
		this->hasChildren = false;
	}

	void SetMedian(T median)
	{
		medianBoundary = median;
	}

	T GetMedian()
	{
		return medianBoundary;
	}

	bool CheckTriangleRayIntersection(Vec3<T> &origVec, Vec3<T> &dirVec,Triangle<T> * &intersectedTriangle)
	{
		for(int trinagleIndex = 0; trinagleIndex < children.size(); trinagleIndex++)
		{
			Triangle<T> * currentTriangle = this->children[trinagleIndex];
				
			if(currentTriangle->CheckRayIntersection(origVec, dirVec))
			{
				intersectedTriangle = currentTriangle;
				return true;
			}
		}
		
		return false;
	}


	void GetVector(Vec3<float> &output, Vec3<float> secondVector, Vec3<float> thirdVector)
	{
		output.x = secondVector.x - thirdVector.x;
		output.y = secondVector.y - thirdVector.y;
		output.z = secondVector.z - thirdVector.z;
	}
	
	void CreateBoundingBox(vector<Triangle<T>*> &nodeObjects)
	{
		Triangle<T> *currentTrianle = nodeObjects[0];

		this->boundingBox = new BoundingBox<T>(currentTrianle->GetTrinagleMidpoint());
		
		for(int index = 0; index < nodeObjects.size(); index ++)
		{
			currentTrianle = nodeObjects[index];
			this->boundingBox->Expand(currentTrianle->vertA);
			this->boundingBox->Expand(currentTrianle->vertB);
			this->boundingBox->Expand(currentTrianle->vertC);
		}
	}

	bool CheckIntersection(Vec3<T> &o, Vec3<T> &d)
	{ 
		return this->boundingBox->CheckIntersection(o,d);
	}

	Vec3<T> GetBoxIntersection(Vec3<T> o, Vec3<T> d)
	{
		return this->boundingBox->GetLineBoxIntersection(o, d);
	}

	void SetPlaneSubDivision(int subDivision)
	{
		plandeSubDivision = subDivision;
	}

	int GetPlaneSubDivision()
	{
		return this->plandeSubDivision;
	}
};



bool SortByZAxis(Triangle<float> *x, Triangle<float> *y)
{
	return min(x->vertA.z,min(x->vertB.z, x->vertC.z)) < min(y->vertA.z, min(y->vertB.z, y->vertC.z));
};

bool SortByYAxis(Triangle<float> *x, Triangle<float> *y)
{
	return min(x->vertA.y,min(x->vertB.y, x->vertC.y)) < min(y->vertA.y, min(y->vertB.y, y->vertC.y));
};

bool SortByXAxis(Triangle<float> *x, Triangle<float> *y)
{
	return min(x->vertA.x,min(x->vertB.x, x->vertC.x)) < min(y->vertA.x, min(y->vertB.x, y->vertC.x));
};



template <typename T>
class KdTree
{
private:

	KdNode<T> *rootNode;

public:
	KdTree(vector<Triangle<T>*> &allObjects)
	{
		rootNode = new KdNode<T>(NULL);
		createTree(allObjects, this->rootNode, 0);
	}

	void createTree(vector<Triangle<T>*> allObjects, KdNode<T> *currentNode, int depth)
	{

		T xAxisLength = 0;
		T yAxisLEngth = 0;
		T zAxisLength = 0;

		T minXAxis = INT_MAX;
		T maxXAxis = INT_MIN;
		T minYAxis = INT_MAX;
		T maxYAxis =  INT_MIN;
		T minZAxis = INT_MAX;
		T maxZAxis = INT_MIN;

		for(int index = 0; index < allObjects.size(); index++ )
		{
			Triangle<T> *chosenNumber = allObjects[index];

			minXAxis = min(min(chosenNumber->vertA.x, min(chosenNumber->vertB.x, chosenNumber->vertC.x)), minXAxis);
			maxXAxis = max(max(chosenNumber->vertA.x, max(chosenNumber->vertB.x, chosenNumber->vertC.x)), maxXAxis);
			minYAxis = min(min(chosenNumber->vertA.y, min(chosenNumber->vertB.y, chosenNumber->vertC.y)), minYAxis);
			maxYAxis = max(max(chosenNumber->vertA.y, max(chosenNumber->vertB.y, chosenNumber->vertC.y)), maxYAxis);
			minZAxis = min(min(chosenNumber->vertA.z, min(chosenNumber->vertB.z, chosenNumber->vertC.z)), minZAxis);
			maxZAxis = max(max(chosenNumber->vertA.z, max(chosenNumber->vertB.z, chosenNumber->vertC.z)), maxZAxis);
		}
			
		currentNode->boundingBox = new BoundingBox<T>(Vec3<T>(minXAxis, minYAxis, minZAxis), Vec3<T>(maxXAxis, maxYAxis, maxZAxis));

		if(allObjects.size() <= 20 || depth >= 50)
		{
			//this will be a leaf node
			currentNode->hasChildren = true;
			currentNode->children = allObjects;

			currentNode->CreateBoundingBox(allObjects);
		}
		else
		{
			xAxisLength = maxXAxis - minXAxis;
			yAxisLEngth = maxYAxis - minYAxis;
			zAxisLength = maxZAxis - minZAxis;
			
			if(xAxisLength > yAxisLEngth && xAxisLength > zAxisLength)
			{
				cout << "sorting by x axis" << endl;
				currentNode->SetPlaneSubDivision(0);
				sort(allObjects.begin(), allObjects.end(), SortByXAxis);
			}
			else if(yAxisLEngth > xAxisLength && yAxisLEngth > zAxisLength)
			{
				cout << "sorting by y axis" << endl;
				currentNode->SetPlaneSubDivision(1);
				sort(allObjects.begin(), allObjects.end(), SortByYAxis);
			}
			else 
			{
				cout << "sorting by z axis" << endl;
				currentNode->SetPlaneSubDivision(2);
				sort(allObjects.begin(), allObjects.end(), SortByZAxis);
			}


			int middleVector = allObjects.size() % 2 == 0? allObjects.size()/ 2 - 1 : allObjects.size() / 2;
			Triangle<T> *chosenNumber = allObjects[middleVector];
			
			//arrange this part
			if(currentNode->plandeSubDivision == 0)
			{
				currentNode->medianBoundary = chosenNumber->GetTrinagleMidpoint().x;
			}
			else if(currentNode->plandeSubDivision == 1)
			{
				currentNode->medianBoundary = chosenNumber->GetTrinagleMidpoint().y;
			}
			else 
			{
				currentNode->medianBoundary = chosenNumber->GetTrinagleMidpoint().z;
			}

			
			vector<Triangle<T>*> leftChildren;
			vector<Triangle<T>*> rightChildren;

			for(int index  = 0; index < allObjects.size(); index ++)
			{
				Triangle<T> * currentTriangle = allObjects[index];

				switch (currentNode->plandeSubDivision)
				{
				case 0:
					if(currentTriangle->GetTrinagleMidpoint().x <= currentNode->medianBoundary)
					{
						leftChildren.push_back(currentTriangle);
					}
					else
					{
						rightChildren.push_back(currentTriangle);
					}
					break;

				case 1:
					if(currentTriangle->GetTrinagleMidpoint().y <= currentNode->medianBoundary)
					{
						leftChildren.push_back(currentTriangle);
					}
					else
					{
						rightChildren.push_back(currentTriangle);
					}
					break;

				case 2:
					if(currentTriangle->GetTrinagleMidpoint().z <= currentNode->medianBoundary)
					{
						leftChildren.push_back(currentTriangle);
					}
					else
					{
						rightChildren.push_back(currentTriangle);
					}
					break;
				default:
					break;
				}
			}

			if(leftChildren.size() > 0)
			{

				KdNode<T> *leftChild = new KdNode<T>(currentNode);
				currentNode->leftChild = leftChild;
				createTree(leftChildren, leftChild, ++depth);
			}
			else
			{
				currentNode->leftChild = NULL;
			}

			if(rightChildren.size() > 0)
			{
				KdNode<T> *rightChild = new KdNode<T>(currentNode);
				currentNode->rightChild = rightChild;
				createTree(rightChildren, rightChild, ++depth);
			}
			else
			{
				currentNode->rightChild = NULL;
			}

			currentNode->hasChildren = false;

			
			
			
		}
	}

	void static SplitByX(vector<Triangle<T>*> &leftChildren, vector<Triangle<T>*> &rightChildren, Triangle<T> *currentTriangle, T median)
	{
		if(currentTriangle->GetTrinagleMidpoint().x > median)
		{
			rightChildren.push_back(currentTriangle);
		}
		else
		{
			leftChildren.push_back(currentTriangle);
		}
	}

	void static SplitByY(vector<Triangle<T>*> &leftChildren, vector<Triangle<T>*> &rightChildren, Triangle<T> *currentTriangle, T median)
	{
		if(currentTriangle->GetTrinagleMidpoint().y > median)
		{
			rightChildren.push_back(currentTriangle);
		}
		else
		{
			leftChildren.push_back(currentTriangle);
		}
	}

	void static SplitByZ(vector<Triangle<T>*> &leftChildren, vector<Triangle<T>*> &rightChildren, Triangle<T> *currentTriangle, T median)
	{
		if(currentTriangle->GetTrinagleMidpoint().z > median)
		{
			rightChildren.push_back(currentTriangle);
		}
		else
		{
			leftChildren.push_back(currentTriangle);
		}
	}

	bool GetIntersection(Vec3<T> &o, Vec3<T> &d, Triangle<T> * &intersectedTriangle)
	{
		Ray<T> *ray = new Ray<T>(o,d);
		return CheckIntersection(ray, this->rootNode, intersectedTriangle);
	}

	bool CheckIntersection(Ray<T> * ray, KdNode<T> *currentNode, Triangle<T> * &intersectedTriangle)
	{	
		if(currentNode->children.size() > 0)
		{
			return currentNode->CheckTriangleRayIntersection(ray->orig, ray->dir, intersectedTriangle);
		}
		else
		{
			if(currentNode->CheckIntersection(ray->orig, ray->dir))
			{
				Vec3<T> intersectionPoint = currentNode->boundingBox->GetLineBoxIntersection(ray->orig, ray->dir);
				T amount = 0;


				if(currentNode->plandeSubDivision == 0)
				{
					if(intersectionPoint.x <= currentNode->medianBoundary)
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->leftChild, intersectedTriangle);
						}
						else 
						{
							return false;
						}
						
					}
					else
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->rightChild, intersectedTriangle) ;
						}
						else 
						{
							return false;
						}
					}
				}
				else if(currentNode->plandeSubDivision == 1)
				{
					if(intersectionPoint.y <= currentNode->medianBoundary)
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->leftChild, intersectedTriangle) ;
						}
						else 
						{
							return false;
						}
						
					}
					else
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->rightChild, intersectedTriangle) ;
						}
						else 
						{
							return false;
						}
					}
				}
				else
				{
					if(intersectionPoint.z <= currentNode->medianBoundary)
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->leftChild, intersectedTriangle) ;
						}
						else 
						{
							return false;
						}
						
					}
					else
					{
						if(currentNode->leftChild != NULL)
						{
							CheckIntersection(ray, currentNode->rightChild, intersectedTriangle) ;
						}
						else 
						{
							return false;
						}
					}
				}
			}
			else
			{
				return false;
			}
		}
	}
};

#endif 